// run: $exec < input
#include <iostream>
#include <algorithm>
#include <vector>

int const maxn = 20007;
int const inf = 1 << 27;

int parent_to_son[maxn];
int son_to_son[maxn];
int cut[maxn];
int parent[maxn];
int rank[maxn];
int ancestor[maxn];
int color[maxn];
int vis_color[maxn];
bool vis[maxn];

int n, m, ans;
std::vector<int> graph[maxn];
std::vector<int> not_tree[maxn];
std::vector<int> tree[maxn];

void make_set(int u)
{
	parent[u] = u;
	rank[u] = 0;
}

int find(int u)
{
	return (parent[u] == u) ? u : (parent[u] = find(parent[u]));
}

void set_union(int u, int v)
{
	int uroot = find(u);
	int vroot = find(v);
	if (rank[uroot] > rank[vroot])
		parent[uroot] = vroot;
	else if (uroot != vroot) {
		parent[vroot] = uroot;
		rank[uroot]++;
	}
}

bool in_same_set(int u, int v)
{
	return find(u) == find(v);
}

void tarjan_offline_lca(int u)
{
	vis[u] = true;
	make_set(u);
	ancestor[u] = u;
	for (int i = 0; i < (int)graph[u].size(); i++) {
		int v = tree[u][i];
		if (vis[v]) continue;
		tarjan_offline_lca(v);
		set_union(u, v);
		ancestor[find(u)] = u;
	}
	color[u] = 1;

	for (int i = 0; i < (int)not_tree[u].size(); i++) {
		int v = not_tree[u][i];
		if (color[v]) {
			int ances = ancestor[find(v)];
			son_to_son[ances]++;
		}
	}
}

void init_son_to_node(int u)
{
	vis_color[u] = 1;
	for (int i = 0; i < (int)tree[u].size(); i++) {
		int v = tree[u][i];
		if (vis_color[u]) continue;
		init_son_to_node(v);
		set_union(u, v);
	}
	for (int i = 0; i < n; i++) {
		int v = graph[u][i];
		if (vis_color[v] == 2 && in_same_set(u, v)) parent_to_son[u]++;
	}
	vis_color[u] = 2;
}

void dfs(int u)
{
	vis[u] = true;
	cut[u] = int(graph[u].size()) - parent_to_son[u];
	for (int i = 0; i < (int)tree[u].size(); i++) {
		int v = tree[u][i];
		if (vis[v]) continue;
		dfs(v);
		cut[u] += cut[v];
		son_to_son[u] += son_to_son[v];
	}
	cut[u] -= 2 * son_to_son[u];
	ans = std::min(ans, cut[u]);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T;
	std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case #" << ti << ": ";
		std::cin >> n >> m;
		for (int i = 0; i < n; i++) {
			graph[i].clear();
			tree[i].clear();
			not_tree[i].clear();
		}
		for (int i = 1, x, y; i < n; i++) {
			std::cin >> x >> y;
			x--; y--;
			graph[x].push_back(y);
			graph[y].push_back(x);
			tree[x].push_back(y);
			tree[y].push_back(x);
		}
		for (int i = 0, x, y; i < m - n + 1; i++) {
			std::cin >> x >> y;
			x--; y--;
			graph[x].push_back(y);
			graph[y].push_back(x);
			not_tree[x].push_back(y);
			not_tree[y].push_back(x);
		}

		for (int i = 0; i < n; i++) {
			make_set(i);
			vis[i] = false;
			cut[i] = 0;
			vis_color[i] = 0;
			son_to_son[i] = 0;
			parent_to_son[i] = 0;
		}
		init_son_to_node(0);
		tarjan_offline_lca(0);

		for (int i = 0; i < n; i++) vis[i] = false;
		ans = inf;
		dfs(0);
		std::cout << ans << '\n';
	}
}

